import java.util.*;

public class 城市群数量2 {
    //通过多源bfs来实现
    public static int n;
    public static boolean[] vis;

    public int citys (ArrayList<ArrayList<Integer>> t) {
        n = t.size();
        vis = new boolean[n];
        int ret = 0;
        //每个城市判断
        for(int i = 0;i < n;i++){
            if(!vis[i]){
                ret++;
                bfs(t,i);
            }
        }
        return ret;
    }

    private void bfs(ArrayList<ArrayList<Integer>> t,int pos){
        //开始标记一下已经搜索过了
        vis[pos] = true;
        Queue<Integer> q = new LinkedList<>();
        q.add(pos);
        //开始搜索
        while(!q.isEmpty()){
            int size = q.size();
            //多源bfs
            while(size-- > 0){
                int a = q.poll();
                for(int i = 0;i < n;i++){
                    if(t.get(i).get(a) == 1 && !vis[i]){
                        vis[i] = true;
                        q.add(i);
                    }
                }
            }
        }
    }
}
